package first

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

/*
	给定一棵二叉搜索树，请找出其中第k大的节点。
	示例 1:

	输入: root = [3,1,4,null,2], k = 1
	   3
	  / \
	 1   4
	  \
	  2
	输出: 4
	示例 2:

	输入: root = [5,3,6,2,4,null,null,1], k = 3
		   5
		  / \
		 3   6
		/ \
	   2   4
	  /
	 1
	输出: 4

	限制：

	1 ≤ k ≤ 二叉搜索树元素个数

	来源：力扣（LeetCode）
	链接：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof
	著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
func kthLargest(root *TreeNode, k int) int {
	// 对bt进行中序遍历得到有序数组
	result := make([]int, 0)
	inorder(root, &result)
	return result[len(result)-k]
}

func inorder(root *TreeNode, result *[]int) {
	if nil == root {
		return
	}
	inorder(root.Left, result)
	*result = append(*result, root.Val)
	inorder(root.Right,result)
}